package com.example.demo.node;

import java.util.HashMap;
import java.util.Map;

/**
 * 交叉链表
 *
 * @author GXYH
 * @date 2021/08/13
 */
public class IntersectionListNode {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 解法1
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        //定义两个头节点，每个节点都一步一步走，到底从头来，相遇则返回
        ListNode a = headA, b = headB;
        while (a != b) {
            a = a.next;
            b = b.next;
            //如果两个都走到了末端，则不相交
            if (a == null && b == null) {
                return null;
            }
            if (a == null) {
                a = headA;
            }
            if (b == null) {
                b = headB;
            }
        }
        return a;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Map<ListNode, ListNode> listNodeMap = new HashMap<>();
        ListNode a = headA, b = headB;
        while (a != null) {
            listNodeMap.put(a, a);
            a = a.next;
        }
        while (b != null) {
            ListNode listNode = listNodeMap.get(b);
            if (listNode != null) {
                return listNode;
            }
            b = b.next;
        }
        return null;
    }

}
